//https://leetcode.cn/problems/maximum-product-subarray/

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();

        vector<int> f(n + 1);
        auto g = f;

        f[0] = g[0] = 1;

        for (int i = 1; i <= n; i++)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = max(nums[i - 1], nums[i - 1] * f[i - 1]);
                g[i] = min(nums[i - 1], nums[i - 1] * g[i - 1]);
            }
            else
            {
                f[i] = max(nums[i - 1], nums[i - 1] * g[i - 1]);
                g[i] = min(nums[i - 1], nums[i - 1] * f[i - 1]);
            }
        }

        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            ret = max(ret, f[i]);
        }

        return ret;

    }
};